package datastructure.sort;

/**
 * @author yinlei
 * @date 2018/6/29
 * @since 1.0.0
 */
public class QuickSort implements SortMain.Sort {
    public void sort(int[] array) {
//        quickSort(array, 0, array.length - 1);
        qsort1(array, 0, array.length - 1);
    }

    // 单向排序
    static public void qsort1(int[] a, int p, int r) {
        // 0个或1个元素，返回
        if (p >= r)
            return;
        // 选择左端点为pivot
        int x = a[p];
        int j = p;
        for (int i = p + 1; i <= r; i++) {
            // 小于pivot的放到左边
            if (a[i] < x) {
                swap(a, ++j, i);
            }
        }
        // 交换左端点和pivot位置
        swap(a, p, j);
        // 递归子序列
        qsort1(a, p, j - 1);
        qsort1(a, j + 1, r);
    }

    // 双向排序
    private static void quickSort(int[] array, int s, int e) {
        if (s >= e) return;
        int mid = (s + e) / 2;
        int val = array[mid];
        swap(array, s, mid);

        int left = s + 1;
        int right = e;

        while (true) {

            while (array[left] <= val && left < right) {
                left++;
            }

            while (array[right] > val) {
                right--;
            }
            if (left >= right) break;
            swap(array, left, right);
        }

        swap(array, s, right);

        quickSort(array, s, right - 1);
        quickSort(array, right + 1, e);
    }

    private static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}
